/****************************************************************************/
/*
* avl tree for xml.
*/
/****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <netinet/in.h>	/*for ntohl*/
#include "cms_common.h"
#include "libmdm.h"
#include "cms_mdm.h"

extern cmsXmlCb_t	*xmlShmCb;

/*______________________________________________________________________________
**	strnicmp
**
**	descriptions:
**
**	parameters:
	str1: node's name
	str2: object name, ex. aaa.bbb.ccc
**	local:
**	global:
**	return:
**	called by:
**	call:
**	revision:
**____________________________________________________________________________*/
static int
stricmp(
    char *str1,
    char *str2
)
{
    char ch1, ch2;
    int diff;
 
    if ( str1 == str2 ) {
        return 0;
    } else if ( str1 == NULL ) {
        return -1;
    } else if ( str2 == NULL ) {
        return 1;
    }
 
    while ( 1 ) {
        diff = (ch1 = *str1) - (ch2 = *str2);
        if ( diff < 0 ) {
            if ( (diff != ('A'-'a')) || (ch1 < 'A') || (ch1 > 'Z')) { 
                /* found difference */
                return -1;
            } 
            /* else matched with different letter case -> continue */
        } else if ( diff > 0 ) {
            if ( (diff != ('a'-'A')) || (ch1 < 'a') || (ch1 > 'z') ) {
                /* found difference */
                return 1;
            }
            /* else matched with different letter case -> continue */
        } else if (( ch1 == '\0' )) {
            /* end of str1 && end of str2 */
            break;
        } 
        /* else matched exactly -> continue */
        str1++;
        str2++;
    }


    return 0;
} 

static int height( uint32_t offset )
{
	objectNode_t *node = NULL;
	if( !offset ){
		return -1;
	}
	else{
		node = cmsXmlGetObjRealAddr(xmlShmCb, offset);
		return node->height;
	}
}
/* END */

static int max( int Lhs, int Rhs )
{
	return Lhs > Rhs ? Lhs : Rhs;
}

/*left->next, right->prev*/
/* This function can be called only if oldChild has a left child */
/* Perform a rotate between a oldChild and its left child */
/* Update heights, then return new middle child */

static objectNode_t *singleRotateWithLeft( objectNode_t *oldChild)
{
	objectNode_t *newChild;

	newChild = cmsXmlGetObjRealAddr(xmlShmCb, NTOHDL(oldChild->sibling.tree.next));
	oldChild->sibling.tree.next = newChild->sibling.tree.prev;
	newChild->sibling.tree.prev = HTONDL(cmsXmlGetPtrOffset(xmlShmCb, oldChild));

	/*+1 is for self height*/
	oldChild->height = max(height(NTOHDL(oldChild->sibling.tree.next)), height(NTOHDL(oldChild->sibling.tree.prev))) + 1;
	newChild->height = max(height(NTOHDL(newChild->sibling.tree.next)), oldChild->height) + 1;

	return newChild;  /* New middle child node */
}
/* END */

/* This function can be called only if oldChild has a right child */
/* Perform a rotate between a node oldChild and its right child */
/* Update heights, then return new middle child */

static objectNode_t *singleRotateWithRight( objectNode_t *oldChild )
{
	objectNode_t *newChild;

	newChild = cmsXmlGetObjRealAddr(xmlShmCb, NTOHDL(oldChild->sibling.tree.prev));
	oldChild->sibling.tree.prev = newChild->sibling.tree.next;
	newChild->sibling.tree.next= HTONDL(cmsXmlGetPtrOffset(xmlShmCb, oldChild));

	oldChild->height = max( height( NTOHDL(oldChild->sibling.tree.next)), height( NTOHDL(oldChild->sibling.tree.prev)) ) + 1;
	newChild->height= max( height( NTOHDL(newChild->sibling.tree.prev)), oldChild->height) + 1;

	return newChild;  /* New middle child node */
}

/* This function can be called only if oldChild has a left */
/* child and oldChild's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */

static objectNode_t *doubleRotateWithLeft( objectNode_t *oldChild )
{
	objectNode_t *node, *next;
	/* Rotate between oldChild->next and oldChild->next->prev */
	next = cmsXmlGetObjRealAddr(xmlShmCb, NTOHDL(oldChild->sibling.tree.next));
	node = singleRotateWithRight(next);
	oldChild->sibling.tree.next = HTONDL(cmsXmlGetPtrOffset(xmlShmCb, node));

	/* Rotate between oldChild and oldChild->next */
	return singleRotateWithLeft( oldChild );
}


/* This function can be called only if oldChild has a right */
/* child and oldChild's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */

static objectNode_t *doubleRotateWithRight( objectNode_t *oldChild )
{
	objectNode_t *node, *prev;
	/* Rotate between oldChild's prev and oldChild->prev->next*/
	prev = cmsXmlGetObjRealAddr(xmlShmCb, NTOHDL(oldChild->sibling.tree.prev));
	node = singleRotateWithLeft(prev);
	oldChild->sibling.tree.prev = HTONDL(cmsXmlGetPtrOffset( xmlShmCb, node ));

	/* Rotate between oldChild and oldChild->prev */
	return singleRotateWithRight( oldChild );
}


objectNode_t *avlInsert( objectNode_t *oldNode, objectNode_t *addNode)
{	
	char *oldName, *addName, *nodeName;
	objectNode_t *tmp, *newChild = NULL, *node = NULL;
	int ret = 0;
	cmsoffset_t offset = 0;
	
	if( oldNode == NULL )
	{
		/*the first node on this level*/
		addNode->height = 0;
		return addNode;
	}

	offset = NTOHDL(oldNode->name);
	oldName = cmsXmlGetObjRealAddr(xmlShmCb, offset);
	offset = NTOHDL(addNode->name);
	addName = cmsXmlGetObjRealAddr(xmlShmCb, offset);
	ret = stricmp(addName, oldName);
	newChild = addNode;
	if( ret < 0)
	{
		if (oldNode->sibling.tree.next){
			node = cmsXmlGetObjRealAddr(xmlShmCb, NTOHDL(oldNode->sibling.tree.next));
		}
		tmp = avlInsert(node, addNode);
		oldNode->sibling.tree.next = HTONDL(cmsXmlGetPtrOffset(xmlShmCb, tmp));
		if( height( NTOHDL(oldNode->sibling.tree.next) ) - height( NTOHDL(oldNode->sibling.tree.prev)) == 2 ){

			offset = NTOHDL(tmp->name);
			nodeName = cmsXmlGetObjRealAddr(xmlShmCb, offset);
			if (stricmp(addName, nodeName) < 0){
				/*LL rotation*/
				newChild = singleRotateWithLeft(oldNode);
			}
			else{
				/*LR rotation*/
				newChild = doubleRotateWithLeft(oldNode);
			}
		}
		else{
			newChild = oldNode;
		}
	}
	else if( ret > 0 )
	{
		if (oldNode->sibling.tree.prev){
			node = cmsXmlGetObjRealAddr(xmlShmCb, NTOHDL(oldNode->sibling.tree.prev));
		}
		tmp = avlInsert(node, addNode);
		oldNode->sibling.tree.prev = HTONDL(cmsXmlGetPtrOffset(xmlShmCb, tmp));	
		if( height( NTOHDL(oldNode->sibling.tree.prev) ) - height( NTOHDL(oldNode->sibling.tree.next)) == 2 ){

			offset = NTOHDL(tmp->name);
			nodeName = cmsXmlGetObjRealAddr(xmlShmCb, offset);
			if (stricmp(addName, nodeName) > 0){
				/*LL rotation*/
				newChild = singleRotateWithRight(oldNode);
			}
			else{
				/*LR rotation*/
				newChild = doubleRotateWithRight(oldNode);

			}
		}
		else{
			newChild = oldNode;
		}		

	}
	/* Else addNode is in the tree already; we'll do nothing */

	newChild->height= max( height( NTOHDL(newChild->sibling.tree.next)), height( NTOHDL(newChild->sibling.tree.prev)) ) + 1;
	return newChild;
}
